package DoblePointer;//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
//
// 示例 4: 
//
// 
//输入: s = ""
//输出: 0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 5 * 10⁴ 
// s 由英文字母、数字、符号和空格组成 
// 
// Related Topics 哈希表 字符串 滑动窗口 👍 6078 👎 0

/**
 * 给定一个字符串,查找字符串中最长的没有重复自负的子串的长度,并返回下对应的起始下标
 * 如果有多个,返回第一个
 *
 * */
import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class lengthOfLongestSubstring {

    public static int[] lengthOfLongestSubstring(String s) {
        int n=s.length();
        int max = 0;
        int index = 0;
        Map<Character, Integer> map = new HashMap<>();
        /**
         * start记录不重复的开始位置
         * end正常遍历指针
         * */
        for (int end = 0, start = 0; end < n; end++) {
            //如果有重复的值，则修改start位置到发现的重复位置的下一个位置
            char c = s.charAt(end);
            if(map.containsKey(c)){
                start = Math.max(map.get(c)+1, start);
//                start = map.get(c)+1;
            }
            //记录最大值
            if(end-start+1 > max){
                max = end-start+1;
                index = start;
            }
            //将当前元素和最新出现的下标放入map中
            map.put(c,end);
        }
        //返回最长长度，和下标
        return new int[]{max,index};
    }

    //返回最长长度
    public static int lengthOfLongestSubstring1(String s) {
        if(s==null || s.length()==0){
            return 0;
        }
        int len = s.length();
        if(len<2){
            return len;
        }

        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        while(right<len){
            char r = s.charAt(right);
            //将当前字符放入
            map.put(r,map.getOrDefault(r,0)+1);
            //如果hash有重复
            while(!isValid(map)){
                char c = s.charAt(left);
                map.put(c,map.get(c)-1);
                if(map.get(c)==0){
                    map.remove(c);
                }
                left++;
            }
            right++;
            res = Math.max(res,map.size());
        }
        return res;
    }

    private static boolean isValid(HashMap<Character, Integer> map){
        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        for(Map.Entry<Character, Integer> entry : entries){
            if(entry.getValue()>1){
                return false;
            }
        }
        return true;

    }

    public static void main(String[] args) {
//        System.out.println(Arrays.toString(lengthOfLongestSubstring("abcabcdbb")));
        System.out.println(lengthOfLongestSubstring1("abcabcdbb"));
    }

}
//leetcode submit region end(Prohibit modification and deletion)
